#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include<queue>
#include<set>
#include<unordered_set>
#define MOD 1000000007

class Solution
{
public:
    int ladderLength(std::string beginWord, std::string endWord, std::vector<std::string>& wordList)
    {
        std::unordered_set<std::string> dic(wordList.begin(), wordList.end());
        std::unordered_set<std::string> small;
        std::unordered_set<std::string> big;
        std::unordered_set<std::string> next;
        if (dic.find(endWord) == dic.end()) return 0;
        int leve=2;
        small.insert(beginWord);
        big.insert(endWord);
        while (!small.empty())
        {
            
           for (const auto& word : small)
           {
               // 为 char 数组分配足够的空间
               std::vector<char> c(word.length() + 1);
               // 将 std::string 内容复制到 vector 中
               strcpy_s(c.data(), c.size(), word.c_str());
               // 现在可以使用 c 数组
               for (int i=0;i<word.length();i++)
               {
                   char now = c[i];
                   for (int j=0;j<26;j++)
                   {
                       c[i] = 'a'+j;
                       std::string newWord(c.data());
                       if (newWord == word) continue;
                       if (small.find(newWord) == small.end()&&dic.find(newWord) != dic.end())
                       {
                           next.insert(newWord);
                           dic.erase(newWord);
                       }
                       if (big.find(newWord) != big.end())
                       {
                           return leve;
                       }
                   }
                   c[i] = now;
               }
           }

            if (next.size()>big.size())
            {
                small.clear();
                small.insert(big.begin(), big.end());
                big.clear();
                big.insert(next.begin(), next.end());
                next.clear();
            }else
            {
                small.clear();
                small.insert(next.begin(), next.end());
                next.clear();
            }
            leve++; 
        }
        return 0;
    }
};
